package 中等.其他;

/**
 * 一个字符串的 美丽值 定义为：出现频率最高字符与出现频率最低字符的出现次数之差。
 * 比方说，"abaacc" 的美丽值为 3 - 1 = 2 。
 * 给你一个字符串 s ，请你返回它所有子字符串的 美丽值 之和。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/sum-of-beauty-of-all-substrings
 */
public class 所有子字符串美丽值之和_1781 {

    public static void main(String[] args) {

        System.out.println(beautySum("spps"));

    }

    /**
     * 计算以 i 结尾的子字符串，美丽值之和为多少
     * 从 i 遍历到 0 ，维护每个字符出现的次数，计算美丽值
     *
     * @param s
     * @return
     */
    public static int beautySum(String s) {
        int sum = 0;
        char[] chars = s.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            int[] record = new int[26];
            for (int j = i; j >= 0; j--) {
                record[chars[j] - 'a']++;
                int max = 0, min = Integer.MAX_VALUE;
                for (int count : record) {
                    max = Math.max(max, count);

                    if (count > 0) {
                        min = Math.min(min, count);
                    }
                }
                sum += max - min;
            }
        }

        return sum;
    }

}
